﻿#pragma once

#include <Windows.h>
#include <cassert>
#include <algorithm>
#include <mutex>
#include <memory>

#define MAX_BYTES_COUNT (1 << 18) // 单次从内存池中申请的最大内存 256KB
#define MIN_BATCH_COUNT 1   // 所获取内存块的批量下限
#define MAX_BATCH_COUNT 512 // 所获取内存块的批量上限
#define MAX_BARREL_COUNT 208 // thread cache与central cache的最大桶数
#define MAX_PAGES_COUNT 129  // 单个span的最大页数
#define UNIT_PAGE_SHIFT 13 // 一页的大小8KB

class nocopy // 不可拷贝
{
public:
	nocopy() = default;
	nocopy(const nocopy&) = delete;
	nocopy& operator=(const nocopy&) = delete;
};

static inline void* SystemAlloc(size_t kpage) // 从系统中按页申请内存
{
#ifdef _WIN32 // windows系统
	void* ptr = VirtualAlloc(0, kpage << UNIT_PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif __linux__ // linux系统
#endif
	if (ptr == nullptr) throw std::bad_alloc();
	return ptr;
}
static inline void SystemFree(void* ptr) // 释放内存
{
	if (ptr == nullptr) return;
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#elif __linux__ // linux系统
#endif
}

//整体控制在最多10%左右的内碎⽚浪费
//[1,128] 8byte对⻬ freelist[0,16)
//[128+1,1024] 16byte对⻬ freelist[16,72)
//[1024+1,8*1024] 128byte对⻬ freelist[72,128)
//[8*1024+1,64*1024] 1024byte对⻬ freelist[128,184)
//[64*1024+1,256*1024] 8*1024byte对⻬ freelist[184,208)
static inline size_t _Align(size_t sizeBytes, size_t alignShift)
{
	return (sizeBytes + ((1 << alignShift) - 1)) & (~((1 << alignShift) - 1));
}
static inline size_t _Index(size_t alignBytes, size_t alignShift)
{
	return ((alignBytes + (1 << alignShift) - 1) >> alignShift) - 1;
}
static inline size_t Align(size_t sizeByte)
{
	assert(sizeByte); // 申请大小为0的字节

	int align_shift[] = { 3,4,7,10,13 };

	if (sizeByte <= 128)
		return _Align(sizeByte, align_shift[0]);
	else if (sizeByte <= 1024)
		return _Align(sizeByte, align_shift[1]);
	else if (sizeByte <= 8 * 1024)
		return _Align(sizeByte, align_shift[2]);
	else if (sizeByte <= 64 * 1024)
		return _Align(sizeByte, align_shift[3]);
	else
		return _Align(sizeByte, align_shift[4]);
}
static inline size_t Index(size_t alignByte)
{
	assert(alignByte);

	int align_shift[] = { 3,4,7,10,13 };
	int prev_count[] = { 0,16,72,128,184 };

	if (alignByte <= 128)
		return _Index(alignByte, align_shift[0]) + prev_count[0];
	else if (alignByte <= 1024)
		return _Index(alignByte - 128, align_shift[1]) + prev_count[1];
	else if (alignByte <= 8 * 1024)
		return _Index(alignByte - 1024, align_shift[2]) + prev_count[2];
	else if (alignByte <= 64 * 1024)
		return _Index(alignByte - 8 * 1024, align_shift[3]) + prev_count[3];
	else
		return _Index(alignByte - 64 * 1024, align_shift[4]) + prev_count[4];
}

static inline unsigned BatchNum(size_t alignByte) // 计算获取内存的批量
{
	assert(alignByte);

	// 申请的内存块单位大小与获取的内存批量成反比
	int retCount = MAX_BYTES_COUNT / alignByte;
	// 调下限
	retCount = max(MIN_BATCH_COUNT, retCount);
	// 调上限
	retCount = min(MAX_BATCH_COUNT, retCount);

	return retCount;
}
static inline unsigned PagesNum(size_t sizeBytes)
{
	assert(sizeBytes);

	return ((sizeBytes + (1 << UNIT_PAGE_SHIFT) - 1) >> UNIT_PAGE_SHIFT);
}

static inline void*& NextMemoryAddr(void* ptr) { return *(void**)ptr; } // 指针ptr前4/8个字节的信息

typedef uintptr_t PAGE_ID; // 页号
typedef unsigned int PAGE_NUM; // 页数
static inline PAGE_ID AddrToPageID(void* addr) { return (PAGE_ID)addr >> UNIT_PAGE_SHIFT; } // 地址 -> 页号
static inline void* PageIDToAddr(PAGE_ID pageId) { return (void*)(pageId << UNIT_PAGE_SHIFT); } // 页号->地址

class FreeList // 管理小块内存的自由链表
{
public:
	void clear()
	{
		_freelist = nullptr;
		_size = 0;
	}
	void push_front(void* obj)
	{
		assert(obj);

		NextMemoryAddr(obj) = _freelist;
		_freelist = obj;
		++_size;
	}
	void pop_front()
	{
		assert(_freelist);

		_freelist = NextMemoryAddr(_freelist);
		--_size;
	}
	void* front() const
	{
		assert(_freelist);

		return _freelist;
	}
	bool empty() const
	{
		return _size == 0;
	}
	size_t size() const
	{
		return _size;
	}

private:
	void* _freelist = nullptr;
	size_t _size = 0;
};

class Span  // 大块内存的信息描述
{
public:
	PAGE_ID _page_id = 0;
	PAGE_NUM _page_len = 0;

	bool _use_if = false; // 是否正在使用(挂载在CentralCache位置即算使用)
	unsigned _size = 0;// 记录该Span切割后小块内存的大小
	unsigned _use_count = 0; // 正在使用的小块个数

	FreeList _freelist; // 对(由span平均分割后)小块内存的管理;
	Span* _prev = nullptr; // 前一个大块内存的地址
	Span* _next = nullptr; // 下一个大块内存的地址
};

class SpanList // 大块内存的管理 
{
public:
	static void erase(Span* obj) // 将span从所属的带头双向循环链表中剥离出来
	{
		assert(obj);
		assert(obj->_prev && obj->_next);

		auto prev = obj->_prev;
		auto next = obj->_next;
		prev->_next = next;
		next->_prev = prev;

		obj->_prev = obj->_next = nullptr;
	}

	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}
	bool empty()
	{
		assert(_head);
		return _head->_next == _head;
	}
	Span* front()
	{
		assert(!empty());
		return _head->_next;
	}
	Span* GetNoEmptySpan()
	{
		if (empty()) return nullptr;

		auto cur = _head->_next;

		while (cur != _head)
		{
			if (cur->_freelist.empty() == false)
				return cur;
			cur = cur->_next;
		}
		return nullptr;
	}
	void pop_front()
	{
		assert(!empty());
		erase(_head->_next);
	}
	void push_front(Span* obj)
	{
		auto next = _head->_next;

		obj->_next = next;
		obj->_prev = _head;

		next->_prev = obj;
		_head->_next = obj;
	}

private:
	Span* _head; // 头指针
};

template<class T>
class ObjectPool // 定长内存池
{
public:
	T* alloc() // 仅完成内存申请
	{
		std::lock_guard<std::mutex> lock(_mtx);

		// 优先把还回来内存块对象，再次重复利用
		if (_freelist.empty() == false)
		{
			T* obj = (T*)_freelist.front();
			_freelist.pop_front();
			return obj;
		}
		else
		{
			// 剩余内存不够一个对象大小时，则重新开大块空间
			if (_remainBytes < sizeof(T))
			{
				_remainBytes = 128 * 1024;
				_memory = (char*)SystemAlloc(_remainBytes >> UNIT_PAGE_SHIFT);
				if (_memory == nullptr)
					throw std::bad_alloc();
			}

			T* obj = (T*)_memory;
			size_t objSize = sizeof(T) >= sizeof(void*) ? sizeof(T) : sizeof(void*);

			_memory += objSize;
			_remainBytes -= objSize;

			return obj;
		}
	}
	void free(T* obj)
	{
		std::lock_guard<std::mutex> lock(_mtx);
		_freelist.push_front((void*)obj);
	}

	T* New() // 完成内存申请 + 对象初始化
	{
		T* obj = alloc();
		new(obj)T;

		return obj;
	}
	void Delete(T* obj) // 完成内存释放 + 对象销毁
	{
		obj->~T();
		free(obj);
	}

private:
	char* _memory = nullptr; // 指向大块内存的指针
	size_t _remainBytes = 0; // 大块内存在切分过程中剩余字节数
	FreeList _freelist; // 自由链表,管理还回来的小块内存
	std::mutex _mtx; // 互斥锁
};